---
title: "扩散"
created: 2025-11-28
tags:
  - 算法
---

# 扩散

## 题目 [扩散](https://www.lanqiao.cn/paper/3839/problem/1019/)

![[image-e37ce127.png]]

## 思路分析

bfs，dfs好像都可以做

用bfs吧 因为有点像那个多源bfs的板子

很多坑

第一 做2020轮结束 无法每拓展一个点就增加一轮 因为多源 很多是同时做的

这个问题 可以用多传一个参数 表示该点是第几轮来解决

第二 地图是无限大的 一开始想着从0,0到1e4,1e4表示地图 标记过后遍历整个地图看有多少个ture就是答案 其实不然 还可能是-,-的坐标
地图的左下角并不是0,0 但是 我们数组的下标不能为负数 所以 用st标记是不可行的

这个问题 换由hash解决  此外 某点合法的判断也不再需要了 判断≥0 ≤n-1反而错误 因为真实的范围可能为负

**unordered_map<int, unordered_map<int, bool>> visited;** 是一个嵌套的无序映射结构，用于存储二维平面上的访问状态。以下是对这个结构的详细解释：

1. **unordered_map**：

   - **unordered_map** 是 C++ 标准库提供的哈希表实现，它通过哈希函数提供常数时间复杂度的插入和查找操作。与 **map** 不同，**unordered_map** 不保证元素的顺序。
2. **嵌套的 unordered_map**：

   - 外层的 **unordered_map<int, unordered_map<int, bool>>** 使用整数键来映射到内层的 **unordered_map**。外层的整数键代表二维平面中的
     x 坐标。
   - 内层的 **unordered_map<int, bool>** 使用整数键代表 y 坐标，并且其值为布尔类型，表示该位置是否被访问过。
3. **用途**：

   - 这个嵌套结构允许动态地处理和存储任意大的二维平面访问状态，而不需要预先分配大块的内存。它只在访问到某个特定位置时才分配内存，从而节省了空间。
   - 例如，如果我们访问了坐标 (3, 5)，那么 **visited[3][5]** 会被设置为 **true**，表示该位置已经被访问过。
4. **优点**：

   - 避免了使用大块连续内存的需求，尤其在处理大范围的二维平面时非常有用。
   - 提供了灵活性，可以处理非常稀疏的访问数据，而不会浪费不必要的内存。

考虑使用 pair当键 bool当值 但是`std::unordered_map` 默认使用 `std::hash` 来进行哈希计算，而 `std::hash`
对于 `std::pair<int, int>` 没有特化版本。要这样写的话 需要我们自己定义一个特化版本的 `std::hash`。反而更麻烦

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

typedef pair<PII,int> PPI;

const int N=1e4;

const int MAX_TIME=2020;

unordered_map<int, unordered_map<int, bool>> st;

queue<PPI> q;

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

bool isVaild(int x,int y,int t){

	return !st[x][y] && t<=MAX_TIME;

}

void bfs(){

	while(!q.empty()){

		auto cur=q.front();q.pop();

		int ux=cur.first.first,uy=cur.first.second,t=cur.second;

		for(int i=0;i<4;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny,t+1)){

				q.push({{nx,ny},t+1});

				st[nx][ny]=true;

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	q.push({{0,0},0});

	st[0][0]=true;

	q.push({{2020,11},0});

	st[2020][11]=true;

	q.push({{11,14},0});

	st[11][14]=true;

	q.push({{2000,2000},0});

	st[2000][2000]=true;

	bfs();

	int cnt=0;

	for(auto row:st){

		for(auto col:row.second){

			if(col.second)

				cnt++;

		}

	}

	cout<<cnt;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[美丽的2|美丽的2]] 🏠 [[00-冲刺国赛]] ➡️ [[阶乘约数|阶乘约数]]